#include "convexhull.h"
#include <algorithm>
#include <list>

namespace
{
struct PointPtrCmp
{
    bool operator ()(Point * const& p1,Point * const& p2)
    {
        return p1->LessThan(*p2);
    }
};

typedef std::vector<Point *> PointArray;
typedef PointArray::iterator PointIter;
typedef std::list<Point *> PointList;
typedef PointList::reverse_iterator PointListRIter;
typedef PointList::iterator PointListIter;

template<typename iterator>
static PointList GetLine(iterator begin,iterator end)
{
    iterator it = begin;
    PointList list;
    list.push_back(*it);
    ++it;

    bool beginDelete = false;
    while(it != end)
    {
        Point *current = reinterpret_cast<Point *>(*it);
        if(list.size() == 1)
        {
            list.push_back(current);
            ++it;
            continue;
        }

        PointListRIter itl = list.rbegin();
        Point *last_point_in_list = *itl;
        ++itl;
        Point *slast_point_in_list = *itl;

        if(current->PointSite(*slast_point_in_list,*last_point_in_list) != Point::kPointAtRight)
        {
            beginDelete = true;
            list.pop_back();
        }
        else
        {
            if(beginDelete)
            {
                beginDelete = false;
            }
            list.push_back(current);
            ++it;
        }
    }
    return list;
}
}
std::vector<Point *> ConvexHull::BuildConvexHull(const std::vector<Point *> &points)
{
    if(points.size() < 3)
        return std::vector<Point *>(points);

    PointArray sorted_points(points);
    std::sort(sorted_points.begin(),sorted_points.end(),PointPtrCmp());

    PointList upper = GetLine(sorted_points.begin(),sorted_points.end());
    PointList lower = GetLine(sorted_points.rbegin(),sorted_points.rend());


    PointArray ret;
    for(PointListIter it = upper.begin();it != upper.end();++it)
    {
        ret.push_back(*it);
    }
    ret.pop_back();
    for(PointListIter it = lower.begin();it != lower.end();++it)
    {
        ret.push_back(*it);
    }
    ret.pop_back();
    return ret;
}

